#include<iostream>
#include<queue>
using namespace std;
#define maxvertexs 10

typedef struct EdgeNode{
    // int weight; //权值
    struct EdgeNode *next;
    int adjvex;//边所指向的节点
}EdgeNode;
typedef struct verNode{
    char data;//顶点信息
    EdgeNode *firstedge;//以该顶点为起始的第一条边
}VNode,adjList[maxvertexs];
typedef struct GraphAdjList{
    adjList vertices;
    int numEdges,numVertexes;
}GraphAdjList;

bool visited[maxvertexs];
queue<int> Q;
//创建邻接表
void Create(GraphAdjList *G){

    int i,j,k;
    EdgeNode *p;

    printf("输入顶点数和边数:\n");
    scanf("%d%d",&G->numVertexes,&G->numEdges);

    //输入顶点信息
    printf("输入顶点信息:\n");
    for(i=0;i<G->numVertexes;i++){
        getchar();//读取上个缓冲区中的换行，读取%c时需要
        scanf("%c",&G->vertices[i].data);
        G->vertices[i].firstedge=NULL;           //将指向边表的指针初始化 
    } 

    //建立边表
    printf("输入边(Vi,Vj)中的下标i,j:\n"); 
    for(k=0;k<G->numEdges;k++){
        scanf("%d%d",&i,&j);
        p=(EdgeNode *)malloc(sizeof(EdgeNode));
        p->adjvex=j;                                //存储弧头 
        p->next=G->vertices[i].firstedge;            //头插法插入边结点 
        G->vertices[i].firstedge=p;

        //下面代码有向图无,无向图有 
        p=(EdgeNode *)malloc(sizeof(EdgeNode));
        p->adjvex=i;                                //存储弧头 
        p->next=G->vertices[j].firstedge;            //头插法插入边结点 
        G->vertices[j].firstedge=p;
    }
}
void visit(GraphAdjList mg,int v){
    printf("%c->",mg.vertices[v].data);
}
int FirstNeighbor(GraphAdjList mg,int v){
    if(mg.vertices[v].firstedge) 
        return mg.vertices[v].firstedge->adjvex;
    else 
        return -1;
}
/*
*@返回值 返回除了顶点w以外的下一个和顶点v相邻的顶点w'
*/
int NextNeighbor(GraphAdjList mg,int v,int w){
    EdgeNode *p=mg.vertices[v].firstedge;
    while(p->adjvex!=w)
        p=p->next;
    if(NULL!=p->next)
        return p->next->adjvex;
    else
        return -1;
}
/*
*类似于树的层次遍历
*借助队列
*需要标记数组visited[]记录哪些顶点被访问过
*@param v表示从顶点v出发bfs遍历整个图
访问->出队->访问邻接节点(如果没有被访问的就存)-所有邻接点都访问完->从最入队的开始出队
*/
void bfs(GraphAdjList mg,int v){
    visit(mg,v);
    visited[v]=true;
    Q.push(v);
    while(!Q.empty()){
        v=Q.front();
        Q.pop();
        for(int w=FirstNeighbor(mg,v);w>=0;w=NextNeighbor(mg,v,w)){
            //检测v所有邻接点
            if(!visited[w]){
                visit(mg,w);
                visited[w]=true;
                Q.push(w);
            }
        }
    }
}
//考虑到非连通可以从visited[]数组中是否有false判断出来
void bfs_traverse(GraphAdjList mg){
    for(int i=0;i<mg.numVertexes;i++){
        visited[i]=false;
    }
    for(int i=0;i<mg.numVertexes;i++){
        if(!visited[i]){
            bfs(mg,i);
        }
    }
}
void dfs(GraphAdjList mg,int v){
    visit(mg,v);
    visited[v]=true;
    for(int w=FirstNeighbor(mg, v);w>=0;w=NextNeighbor(mg, v, w)){
        if(!visited[w]){
            dfs(mg,w);
        }
    }
}
void dfs_traverse(GraphAdjList mg){
    for(int v=0;v<mg.numVertexes;v++){
        visited[v]=false;
    }
    for(int v=0;v<mg.numVertexes;v++){
        if(!visited[v])
            dfs(mg,v);
    }
}
void print_Mg(GraphAdjList mg){
    printf("邻接表为：\n");
    for(int i=0;i<mg.numVertexes;i++){
        EdgeNode *p=mg.vertices[i].firstedge;
        printf("%c",mg.vertices[i].data);
        while(p){
            printf("->%c->",mg.vertices[p->adjvex].data);
            p=p->next;
        }
        printf("\n");
    }
}
int main(){
    GraphAdjList mg;
    Create(&mg);
    print_Mg(mg);
    printf("\n");
    /*
    *顶点a b c d
    *按照(0,1),(0,2),(2,3)顺序创建边
         a
        / \
       c   b
      /
     d
    因为是头插法所以得到的邻接矩阵如下：
    a->c->->b->
    b->a->
    c->d->->a->
    d->c->
    */
    printf("bfs遍历:");
    bfs(mg,0);//
    //bfs_traverse(mg);
/*
*顶点a b c d e
*按照(0,1),(0,2),(2,3)顺序创建边
     a      e
    / \
   c   b
  /
 d
*得到的邻接矩阵如下:
a->c->->b->
b->a->
c->d->->a->
d->c->
e
*/
    printf("\ndfs遍历:");
    dfs_traverse(mg);
    return 0;
}